package leetcode.nTree;

import datastructure.tree.Node;

import java.util.*;

/**
 * @Description: https://leetcode.cn/problems/n-ary-tree-preorder-traversal/
 * 给定一个 n叉树的根节点 root，返回 其节点值的 前序遍历 。
 * <p>
 * n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
 *
 * 草稿(旧)：4
 *
 * @Author Ammar
 * @Create 2023/3/30 18:18
 */
public class _589_N叉树的前序遍历 {

    /**
     * 递归
     * @param root
     * @return
     */
    public static List<Integer> preorder1(Node root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) return list;
        list.add(root.val);
        if (root.children == null || root.children.size() == 0) return list;
        for (int i = 0; i < root.children.size(); i++) {
            Node node = root.children.get(i);
            // 递归每个节点的前序遍历
            list.addAll(preorder1(node));
        }
        return list;
    }

    /**
     * 遍历 使用栈的特性，将子节点倒序压入栈中。最终出栈的顺序就是前序遍历N叉树
     * @param
     */
    public static List<Integer> preorder(Node root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) return list;
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            list.add(node.val);
            if (node.children != null && node.children.size() != 0) {
                for (int i = node.children.size() - 1; i >= 0; i--) {
                    stack.push(node.children.get(i));
                }
            }
        }
        return list;
    }
}
